package _stack_queue

import org.junit.Assert
import org.junit.Test
import java.util.*

/**
 *
 * https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html
 * https://leetcode.cn/problems/valid-parentheses/description/
 * 20. 有效的括号
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 *
 * 有效字符串需满足：
 *
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 每个右括号都有一个对应的相同类型的左括号。
 *
 * 示例 1：
 * 输入：s = "()"
 * 输出：true
 *
 * 示例 2：
 * 输入：s = "()[]{}"
 * 输出：true
 *
 * 示例 3：
 * 输入：s = "(]"
 * 输出：false
 *
 * 示例 4：
 * 输入：s = "([])"
 * 输出：true
 */
class leetcode_20 {

    @Test
    fun test_1() {
        Assert.assertEquals(true, isValid("()"))
    }

    @Test
    fun test_2() {
        Assert.assertEquals(true, isValid("()[]{}"))
    }

    @Test
    fun test_3() {
        Assert.assertEquals(false, isValid("(]"));
    }

    @Test
    fun test_4() {
        Assert.assertEquals(true, isValid("([])"));
    }

    private fun isValid(s: String): Boolean {
        // T - N
        // S - N
        val array: CharArray = s.toCharArray()
        val stack: LinkedList<Char> = LinkedList<Char>()
        for (ch in array) {
            if (stack.isEmpty()) {
                stack.push(ch)
            } else {
                val top = stack.peek()
                if ((top == '{' && ch == '}') || (top == '(' && ch == ')') || (top == '[' && ch == ']')) {
                    stack.pop()
                } else {
                    stack.push(ch)
                }
            }
        }
        return stack.isEmpty()
    }
}